package com.zhanghp.class036;

import com.zhanghp.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树的锯齿形层序遍历
 * 测试链接 : https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
 *
 * @author zhanghp
 * @since 2024/4/15 16:11
 */
public class Code02_ZigzagLevelOrderTraversal {

    static class Solution {

        public final int MAX_SIZE = 2001;

        public TreeNode[] node = new TreeNode[MAX_SIZE];

        public int l, r;

        /**
         * true:  从右往左
         * false：从左往右
         */
        public boolean reverse = false;

        //
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> ans = new ArrayList<>();
            if (root == null) {
                return ans;
            }
            l = r = 0;
            node[r++] = root;
            while (l < r) {
                int size = r - l;
                List<Integer> nodeValues = new ArrayList<>();
                // 遍历数值
                // reverse == false, 左 -> 右， l....r-1, 收集size个
                // reverse == true,  右 -> 左， r-1....l, 收集size个
                // 左 -> 右, i = i + 1
                // 右 -> 左, i = i - 1
                // i:遍历的索引
                // j:加/减 i
                // k:累计和size比对，跳出for
                for (int i = reverse ? r - 1 : l, j = reverse ? -1 : 1, k = 0; k < size; i += j, k++) {
                    nodeValues.add(node[i].val);
                }
                for (int i = 0; i < size; i++) {
                    TreeNode cur = this.node[l++];
                    if (cur.left != null) {
                        node[r++] = cur.left;
                    }
                    if (cur.right != null) {
                        node[r++] = cur.right;
                    }
                }
                ans.add(nodeValues);
                reverse = !reverse;
            }
            return ans;

        }
    }
}
